// 经典数组操作

/**
 * 随机打乱数组
 */
function shuffleArray<T>(array: Array<T>) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 随机索引
    [array[i], array[j]] = [array[j], array[i]]; // 交换元素
  }
  return array;
}

/**
 * 二分查找（Binary Search）
 * 在一个已排序的数组中，通过不断将搜索区间减半来查找目标值。O(log n)
 */
function binarySearch<T>(arr: Array<T>, target: T) {
  let left = 0,
    right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // 未找到
}

/**
 * 快速排序
 * 通过选择一个“基准”元素，将数组分成两部分，递归排序。
 * 平均时间复杂度为 O(n log n)。
 */
function quickSort<T>(arr: Array<T>): Array<T> {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = arr.slice(0, -1).filter((x) => x < pivot);
  const right = arr.slice(0, -1).filter((x) => x >= pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

/**
 * 深度优先搜索（DFS）
 * 使用栈（递归实现）来进行树或图的遍历。
 */
function dfs(node) {
  if (!node) return;
  console.log(node.value);
  node.children.forEach((child) => dfs(child));
}

/**
 * 广度优先搜索（BFS）
 * 使用队列来逐层遍历树或图。
 */
function bfs(root) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.value);
    queue.push(...node.children);
  }
}

/**
 * 动态规划
 * 通过将复杂问题分解为子问题并存储其结果来优化计算。
 * 典型例子包括 Fibonacci 数列、背包问题等。
 */
function fibonacci(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

/**
 * 合并排序（Merge Sort）
 * 将数组分成小数组，分别进行排序，然后合并。稳定且性能良好。O(n log n)
 */
function mergeSort<T>(arr: Array<T>): Array<T> {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge<T>(left: Array<T>, right: Array<T>) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return [...result, ...left, ...right];
}
